package main.old.new_2023.last.month_6;

import main.dataStruct.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description:
 * todo 1253. 重构 2 行二进制矩阵
 * 给你一个 2 行 n 列的二进制数组：
 * 矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是 0 就是 1。
 * 第 0 行的元素之和为 upper。
 * 第 1 行的元素之和为 lower。
 * 第 i 列（从 0 开始编号）的元素之和为 colsum[i]，colsum 是一个长度为 n 的整数数组。
 * 你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。
 * 如果有多个不同的答案，那么任意一个都可以通过本题。
 * 如果不存在符合要求的答案，就请返回一个空的二维数组。
 * todo 剑指 Offer 34. 二叉树中和为某一值的路径
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 * 叶子节点 是指没有子节点的节点。
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/5
 * @Param:
 * @return:
 **/
public class Solution0629 {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    //二叉树中和为某一值的路径
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recur(root, target);
        return res;
    }
    private void recur(TreeNode root,int tar){
        if(root == null) return;
        path.add(root.val);
        tar = tar - root.val;
        if(tar == 0 && root.left == null && root.right == null){
            res.add(new LinkedList(path));
        }
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }

    //重构 2 行二进制矩阵
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        //colsum 之和 = upper + lower，我感觉就循环colsum
        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        for (int sum:colsum){
            if (upper <0 || lower<0){
                return lists;
            }
            if (sum < 0 || sum >2){
                return lists;
            }else if (sum == 1){
                if (upper >= lower){
                    upper--;
                    a.add(1);
                    b.add(0);
                }else {
                    lower--;
                    a.add(0);
                    b.add(1);
                }
            }else if (sum == 2){
                upper--;
                lower--;
                a.add(1);
                b.add(1);
            }else {
                a.add(0);
                b.add(0);
            }
        }
        if (upper ==0 && lower ==0){
            lists.add(a);
            lists.add(b);
        }
        return lists;
    }
}
